package Test;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @author chenyuan
 */
public class Test {

	public static void main(String[] args) {
		Test test = new Test();

		System.out.println(test.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
	}

	public int maxSubArray(int[] nums) {
		int pre = 0, max = nums[0];
		for (int num : nums) {
			pre = Math.max(pre + num, num);
			max = Math.max(max, pre);
		}
		return max;
	}
}
